Signal reconstruction is used in many signal processing applications, and under various names. In image and video processing, a signal can comprise, e.g., an image, and a goal of the reconstruction can be, e.g., outputting an image at super-resolution, i.e., at a resolution that is higher than an original resolution of the image. Similarly, in audio processing applications, a signal can comprise an audio sequence, wherein the reconstruction can be used, e.g., to increase audio frequency ranges. In data mining applications, signal reconstruction appears in a form of, e.g., data completion. Signal reconstruction, and more particularly analyzing, approximating, denoising and interpolating sampled signals, is practically important and described in numerous patents and publications.
A method and apparatus for waveform reconstruction for sampled signal edges of a repetitive signal data system is disclosed in U.S. Pat. No. 4,928,251. A sequence of relatively low resolution samples of a repetitive input signal with high frequency components is acquired, without triggering, to determine an approximate waveform from the low resolution samples. Then, a fast Fourier transform is applied to a reconstructed time record of the input signal to obtain a frequency for each signal component. The sampled waveform is reconstructed by overlaying sampled components with reference to a common time or phase.
A system for reconstruction of non-uniformly sampled signals is disclosed in U.S. Pat. No. 7,403,875. The non-uniformly sampled signal includes a sampled signal and an amplitude error between the signal sampled with an equidistant sample period and the non-uniformly sampled signal. A reconstructed amplitude error is determined through a time offset and the non-uniformly sampled signal. The amplitude error is subtracted from the non-uniformly sampled signal.
A method and system for super-resolution signal reconstruction from an input field is disclosed in U.S. publication 20120188368. The method comprises: providing measured data corresponding to output field of the measurement system; providing data about sparsity of the input field, and data about effective response function of the measurement system; and processing the measured data based on the known data. The processing first determines a sparse vector as a function of the measured data, along with a set indicating the sparsity of the input field, and the effective response function. The sparse vector is then used for reconstructing the input information.
U.S. Pat. No. 4,774,565 discloses a method for sensing scene light and providing sampled image data in three colors. The sampled image data is subsequently interpolated for the non-sampled colors and thereafter subtracted to provide two color difference signals. The two color difference signals, in turn, are each median filtered and subsequently reconstructed in conjunction with the originally sampled image data to reduce the color fringing in the reconstructed image.
A real-time super-resolution method is disclosed in U.S. Pat. No. 5,748,507. In that method, a super-resolution technique of constrained total least squares is used to extend samples of input signals for higher resolution spectral analysis and output.
A reconstruction method using a Hilbert transform is disclosed in U.S. Pat. No. 7,424,088. The method determines an image data value at a point of reconstruction in a computed tomography (CT) image of a scanned object, filtering the obtained projection data with a one-dimensional ramp filter to generate ramp-filtered data, and applying a backprojection operator with inverse distance weighting to the ramp-filtered data to generate the image data value at the point of reconstruction in the CT image.
A method for reconstruction of sparse frequency spectrum from ambiguous under-sampled time domain data is disclosed in U.S. publication 20140232581. The method converts a high bandwidth analog signal to a digital signal. The method splits a high bandwidth analog signal into parallel channels with increasing delays. Each channel is then sampled at a sub-Nyquist frequency smaller than the high bandwidth signal. The channels are then upsampled at the Nyquist frequency of the high bandwidth signal and combined to generate a digital signal representing the high bandwidth analog signal.
A method for reconstructing signals from inaccurate measurements due to quantization is disclosed in U.S. Pat. No. 5,587,711. Non-linear filtering is applied to a quantized signal to distribute quantum changes over their respective time intervals to provide, for example, a smoother reconstructed signal. The quantization bounds are enforced for each refined signal point to ensure a reconstructed signal that is within the bounded uncertainty associated with the original signal.
U.S. publication 20120150544 discloses a method for reconstructing speech from an input signal comprising whispers. The method analyses the input signal to form a representation of the input signal that is then modified to adjust the spectrum of the signal. The modification changes the bandwidth of at least one formant in the spectrum to achieve a predetermined spectral energy distribution and amplitude for the at least one formant.
Sampling theories are important for signal processing systems and applications, such as generating super-resolution images, processing biomedical imaging, sampling rate conversion for acoustic signals, and graph based signal interpolation.
One example is the reconstruction of band-limited signals from samples acquired in the time domain, see Unser et al. “A general sampling theory for non-ideal acquisition devices,” Signal Processing, IEEE Transactions on, 42(11):2915-2925, 1994. Several extensions of a Shannon-Hartley theorem are developed based on viewing sampling in a broader sense of a projection onto appropriate subspaces and then selecting the subspaces according to specific applications; see Eldar et al., “Beyond bandlimited sampling,” Signal Processing Magazine, IEEE, 26(3):48-68, 2009.
More recently, the reconstruction of signals on graphs, band-limited with respect to eigenvalues of the graph Laplacian, from signal samples on a subset of nodes of the graph has gained popularity, e.g., see Narang et al., “Signal processing techniques for interpolation in graph structured data,” IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 5445-5449, 2013, and Narang et al., “Localized iterative methods for interpolation in graph structured data,” Global Conference on Signal and Information Processing (GlobalSIP), 2013 IEEE, pages 491-494, December 2013.
One task of the reconstruction is to determine a reconstructed signal of an unknown original signal based on samples of the original signal, where the samples typically belong to a sampling subspace; see Eldar et al., “Beyond bandlimited sampling,” Signal Processing Magazine, IEEE, 26(3):48-68, 2009. Searching for reconstructed signals is commonly performed in a subspace. We refer to the subspace as a guiding subspace. It is often desired to minimize an error, expressed as distance between the unknown original signal and the reconstructed signal.
In one prior art method, a consistent reconstruction method is disclosed. A consistency condition ensures that the reconstructed signal always yields the same samples in the sampling subspace as the original signal. In addition, it is required that the direct sum of the guiding subspace and the complement of the sampling subspace is equal to the signal space so that an oblique projector can be used in the solution, see Eldar, “Sampling with arbitrary sampling and reconstruction spaces and oblique dual frame vectors,” Journal of Fourier Analysis and Applications, 9(1):77-96, 2003, and Berger et al, “Sampling and reconstruction in different subspaces by using oblique projections,” Technical Report arXiv:1312.1717, December 2013. The requirement that the direct sum of the guiding subspace and the complement of the sampling subspace are equal to the signal space is too restrictive for some applications or can be disadvantageous, e.g., the requirement can lead to oblique projectors with large norms, resulting in unstable reconstruction methods that are very sensitive to signal noise.
To circumvent this requirement, a more general constrained reconstruction minimizes a distance from the reconstructed signal to the sample-consistent reconstruction plane. If the distance is zero, then this reconstruction is sample consistent, otherwise, the reconstruction represents a generalized reconstruction. In most practical applications, all possible consistent reconstructed signals are disjoint from the guiding subspace. Those generalized reconstruction methods place the reconstructed signal into the guiding subspace, making it sample inconsistent, see Berger et al, “Sampling and reconstruction in different subspaces by using oblique projections,” Technical Report arXiv:1312.1717, December 2013.
In a different application area, a bandwidth expansion of a narrowband audio signal, a reconstruction method makes the reconstructed signal consistent, see Bansal et al., “Bandwidth expansion of narrowband speech using non-negative matrix factorization,” Ninth European Conference on Speech Communication and Technology, 2005. Rather than placing the reconstructed signal into the guiding subspace as in Berger et al.
One of key limitation of the prior art signal reconstruction methods is that in practice it may not be clear a priori if the reconstructed signal should be forced into the guiding subspace, or whether the reconstructed signal should be sample consistent, in a practically important case, where the guiding subspace contains no sample consistent signals. The prior art does not cover a situation where, e.g., both procedures, sampling and guiding, can be equally reliable.